//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 
//
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,2,3]
//输出：3 
//
// 示例 2： 
//
// 
//输入：nums = [2,2,1,1,1,2,2]
//输出：2
// 
//
// 
//提示：
//
// 
// n == nums.length 
// 1 <= n <= 5 * 10⁴ 
// -10⁹ <= nums[i] <= 10⁹ 
// 
//
// 
//
// 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。 
//
// Related Topics 数组 哈希表 分治 计数 排序 👍 1964 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-09-19 22:29:31
 * @description 169.多数元素
 */
public class MajorityElement{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new MajorityElement().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*1.排序后的中位数，onlogn
		 * 2.hash计数，空间时间On
		 * 3.摩尔投票法：
		 * 核心就是对拼消耗。
		 * 不同的就消耗，只要相同的大于一半就可以存活
		 * 从第一个开始计数0，相同就+1，不同-1，到0的时候换一个数计数，最后返回t
		 * */
    public int majorityElement3(int[] nums) {
		//诸王争霸赛开始【规则是目前投票数为0的话换候选人，自己人给自己人投票，敌方减票】
		//摩尔投票法为啥成立？因为这里的众数是指大于总数数目的二分之一，举两个个极端例子
		//121311【肯定有相邻的，其他的】或者111123【全部联合起来，敌方都抵消不了】
		int count=1,t=nums[0];
		for (int num : nums) {
			if(num==t){
				//帮派的人来撑腰了，票数++
				count++;
			}else {
			//敌方来骚扰我当霸王，票数--
				count--;
			}
			//没了，目前帮派人不够地方多，话语权没有
			if(count==0) {
				//更换霸王
				t=num;
				count=1;
			}
		}
		return t;
    }
	//投票其他写法
	public int majorityElement1(int[] nums) {
		// return divide(nums, 0, nums.length - 1);
		int cnt = 0;
		int candidate = 0;
		for (int t : nums) {
			if (cnt == 0) {
				candidate = t;
			}
			cnt += (candidate == t) ? 1 : -1;
		}
		return candidate;
	}

	private int countInRange(int[] nums, int num, int lo, int hi) {
		int count = 0;
		for (int i = lo; i <= hi; i++) {
			if (nums[i] == num) {
				count++;
			}
		}
		return count;
	}
		/*分治。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。
		如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。
		如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。
		否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数
		时间空间复杂度：Onlogn
*/
	private int majorityElementRec(int[] nums, int lo, int hi) {
		// base case; the only element in an array of size 1 is the majority
		// element.
		if (lo == hi) {
			return nums[lo];
		}

		// recurse on left and right halves of this slice.
		int mid = (hi - lo) / 2 + lo;
		int left = majorityElementRec(nums, lo, mid);
		int right = majorityElementRec(nums, mid + 1, hi);

		// if the two halves agree on the majority element, return it.
		if (left == right) {
			return left;
		}

		// otherwise, count each element and return the "winner".
		int leftCount = countInRange(nums, left, lo, hi);
		int rightCount = countInRange(nums, right, lo, hi);

		return leftCount > rightCount ? left : right;
	}

	public int majorityElement(int[] nums) {
		return majorityElementRec(nums, 0, nums.length - 1);
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
